package BF_DP;

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length+1];

        for (int i = 2; i <= cost.length ; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }
    public int numDecodings(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] dp = new int[n];
        // 初始化 第一和第二
        if ( chars[0] != '0')dp[0] =1;
        if (n == 1)return dp[0];
        if (chars[1] != '0' && chars[0] != '0')dp[1] +=1;
        int t = (chars[0]-'0')*10+(chars[1]-'0');
        if (t >= 10  && t <=26)dp[1] +=1;

        //填表
        for (int i = 2; i < n; i++) {
            // 第一种情况,单独编码
            if (chars[i] != '0'){
                dp[i] +=dp[i-1];
            }
            int k = (chars[i-1]-'0')*10+(chars[i]-'0');
            if (k >=10 && k <=26)dp[i]+=dp[i-2];

        }
        return dp[n-1];

    }


}